home *** CD-ROM | disk | FTP | other *** search
/ PC Media 4 / PC MEDIA CD04.iso / share / os2 / zoo21_2 / source / lzd.c < prev    next >
C/C++ Source or Header  |  1991-07-14  |  31KB  |  848 lines
  1. #ifndef LINT
  2. static char sccsid[]="@(#) lzd.c 2.6 88/01/30 20:39:18";
  3. #endif /* LINT */
  4.  
  5. /*********************************************************************/
  6. /* This file contains two versions of the lzd() decompression routine.
  7. The default is to use a fast version coded by Ray Gardner.  If the
  8. symbol SLOW_LZD is defined, the older slower one is used.  I have tested
  9. Ray's code and it seems to be portable and reliable.  But if you
  10. suspect any problems you can define SLOW_LZD for your system in
  11. options.h and cause the older code to be used.  --R.D. */
  12. /*********************************************************************/
  13.  
  14. #include "options.h"
  15. #include "zoo.h"
  16. #include "zooio.h"
  17. #include "various.h"
  18. #include "zoofns.h"           /* function definitions */
  19. #include "zoomem.h"
  20. #include "debug.h"
  21. #include "assert.h"
  22. #include "lzconst.h"
  23.  
  24. #ifndef SLOW_LZD
  25.  
  26. /* Extensive modifications for speed by Ray Gardner
  27. ** Public domain by Raymond D. Gardner  9/26/88
  28. **
  29. ** I apologize for the comments being so dense in places as to impair
  30. ** readability, but some of the stuff isn't very obvious and needs
  31. ** some explaining.  I am also sorry for the messy control structure
  32. ** (quite a few labels and goto's) and very long lzd() function, but
  33. ** I don't know how to do this any other way without loss of speed.
  34. **
  35. ** Ray Gardner
  36. ** 6374 S. Monaco Ct.
  37. ** Englewood, CO 80111
  38. */
  39.  
  40. #ifdef ANSI_HDRS
  41. # include <string.h>        /* to get memcpy */
  42. #else
  43.   VOIDPTR memcpy();
  44. #endif
  45.  
  46. #define  STACKSIZE   4000  /* allows for about 8Mb string in worst case? */
  47. /* stack grows backwards in this version, using pointers, not counters */
  48. static char *stack;
  49. static char *stack_pointer;
  50. static char *stack_lim;
  51.  
  52. void init_dtab PARMS((void));
  53. unsigned rd_dcode PARMS((void));
  54. /* void wr_dchar (char); */        /* now a macro */
  55. void ad_dcode PARMS((void));
  56.  
  57. #ifdef FILTER
  58. /* to send data back to zoofilt */
  59. extern unsigned int filt_lzd_word;
  60. #endif /* FILTER */
  61.  
  62. void xwr_dchar PARMS ((char));
  63. static int firstchar PARMS ((int));
  64. static void cbfill PARMS ((void));
  65.  
  66. /* wr_dchar() is a macro for speed */
  67. #define wr_dchar(c) {                             \
  68.                            if (outbufp<outbuflim) \
  69.                               *outbufp++=(char)(c);     \
  70.                            else                   \
  71.                               xwr_dchar((char)c);       \
  72.                     }
  73.  
  74. extern char *out_buf_adr;        /* output buffer */
  75. extern char *in_buf_adr;         /* input buffer */
  76.                       /* use pointers (not counters) for buffer (for speed) */
  77. static char *outbufp;            /* output buffer pointer */
  78. static char *outbuflim;          /* output buffer limit */
  79. static char *outbufguard;        /* output buffer "guard" */
  80.  
  81. char memflag = 0;                /* memory allocated? flag */
  82. int *head;                       /* lzw prefix codes */
  83. char *tail;                      /* lzw suffix codes */
  84. static unsigned cur_code;
  85. static unsigned old_code;
  86. static unsigned in_code;
  87.  
  88. static unsigned free_code;
  89. static int nbits;
  90. static unsigned max_code;
  91.  
  92. /* We use a buffer of codes to avoid a function call to unpack each
  93. ** one as needed.  We allocate an extra slot past the end of the buffer
  94. ** and put a CLEAR code in it, to serve as a sentinel.  This way we can
  95. ** fold the test for code buffer runout into the test for a clear code
  96. ** and avoid having an extra test on each code processed.  Also, we don't
  97. ** always use the code buffer.  We can only use it when the input buffer
  98. ** is at a byte boundary, and when we know that the codesize won't change
  99. ** before we fill the code buffer, and when we know we won't run out of
  100. ** bytes in the input buffer before filling the code buffer.  So we start
  101. ** with the code buffer pointer pointing to the sentinel, and we always
  102. ** have it pointing at the sentinel when we can't (for one reason or
  103. ** another) be getting our codes from the code buffer.  We check for this
  104. ** condition whenever we get a CLEAR code, and if so, we get the code
  105. ** via the good old rd_dcode() routine.
  106. **
  107. ** One other problem with the code buffer approach is that we might get
  108. ** a CLEAR code in the middle of the buffer.  This means that the next
  109. ** code is only 9 bits, but we have probably already unpacked a number of
  110. ** larger codes from the input into the buffer before we discover this.
  111. ** So we remember where (in the input buffer) the code buffer was filled
  112. ** from, and when a CLEAR code is encountered in the buffer (not the
  113. ** sentinel at the end) we back up the bit_offset pointer in the input
  114. ** buffer, and reset things to start unpacking the 9-bit codes from there.
  115. */
  116.  
  117. #define CODEBUF_SIZE 64      /* must be multiple of 8, experiment for best */
  118. static unsigned codebuf[CODEBUF_SIZE+1];     /* code buffer */
  119. static unsigned *codebufp;       /* code buffer pointer */
  120. static unsigned *codebuflim;     /* code buffer limit */
  121.       /* bit offset within the input buffer of where the code buffer began */
  122. static unsigned codebufoffset;
  123.  
  124. static unsigned masks[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
  125.                         0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff };
  126. static unsigned bit_offset;   /* note this only allows max 8K input buffer!!*/
  127.  
  128. #ifdef UNBUF_IO
  129. #define        BLOCKFILE        int
  130. #define        BLOCKREAD        read
  131. #define        BLOCKWRITE        blockwrite
  132. int read PARMS ((int, VOIDPTR, unsigned));
  133. int write PARMS ((int, VOIDPTR, unsigned));
  134. int blockwrite PARMS ((int, VOIDPTR, unsigned));
  135. #else
  136. #define        BLOCKFILE        ZOOFILE
  137. #define        BLOCKREAD        zooread
  138. #define        BLOCKWRITE        zoowrite
  139. #endif /* UNBUF_IO */
  140.  
  141. static BLOCKFILE in_f, out_f;
  142.  
  143. /* rd_dcode() reads a code from the input (compressed) file and returns
  144. its value. */
  145. unsigned rd_dcode()
  146. {
  147.    register char *ptra, *ptrb;    /* miscellaneous pointers */
  148.    unsigned word;                     /* first 16 bits in buffer */
  149.    unsigned byte_offset;
  150.    char nextch;                           /* next 8 bits in buffer */
  151.    unsigned ofs_inbyte;               /* offset within byte */
  152.  
  153.    ofs_inbyte = bit_offset % 8;
  154.    byte_offset = bit_offset / 8;
  155.    bit_offset = bit_offset + nbits;
  156.  
  157.    assert(nbits >= 9 && nbits <= 13);
  158.  
  159.    if (byte_offset >= INBUFSIZ - 5) {
  160.       int space_left;
  161.  
  162.       assert(byte_offset >= INBUFSIZ - 5);
  163.       debug((printf ("lzd: byte_offset near end of buffer\n")))
  164.  
  165.       bit_offset = ofs_inbyte + nbits;
  166.       space_left = INBUFSIZ - byte_offset;
  167.       ptrb = byte_offset + in_buf_adr;          /* point to char */
  168.       ptra = in_buf_adr;
  169.       /* we now move the remaining characters down buffer beginning */
  170.       debug((printf ("rd_dcode: space_left = %d\n", space_left)))
  171.       while (space_left > 0) {
  172.          *ptra++ = *ptrb++;
  173.          space_left--;
  174.       }
  175.       assert(ptra - in_buf_adr == ptrb - (in_buf_adr + byte_offset));
  176.       assert(space_left == 0);
  177.       if (BLOCKREAD (in_f, ptra, byte_offset) == -1)
  178.          prterror ('f', "I/O error in lzd:rd_dcode.\n");
  179.       byte_offset = 0;
  180.    }
  181.    ptra = byte_offset + in_buf_adr;
  182.  /* NOTE:  "word = *((int *) ptra)" would not be independent of byte order. */
  183.    word = (unsigned char) *ptra; ptra++;
  184.    word = word | ( ((unsigned char) *ptra) << 8 ); ptra++;
  185.  
  186.    nextch = *ptra;
  187.    if (ofs_inbyte != 0) {
  188.       /* shift nextch right by ofs_inbyte bits */
  189.       /* and shift those bits right into word; */
  190.       word = (word >> ofs_inbyte) | (((unsigned)nextch) << (16-ofs_inbyte));
  191.    }
  192.    return (word & masks[nbits]);
  193. } /* rd_dcode() */
  194.  
  195. void init_dtab()
  196. {
  197.    nbits = 9;
  198.    max_code = 512;
  199.    free_code = FIRST_FREE;
  200. }
  201.  
  202. /* By making wr_dchar() a macro and calling this routine only on buffer
  203. ** full condition, we save a lot of function call overhead.
  204. ** We also use pointers instead of counters for efficiency (in the macro).
  205. */
  206. void xwr_dchar (ch)
  207. char ch;
  208. {
  209.    if (outbufp >= outbuflim) {      /* if buffer full */
  210.       if (BLOCKWRITE (out_f, out_buf_adr, outbufp - out_buf_adr)
  211.                                                 != outbufp - out_buf_adr)
  212.          prterror ('f', "Write error in lzd:wr_dchar.\n");
  213.       addbfcrc(out_buf_adr, outbufp - out_buf_adr);     /* update CRC */
  214.       outbufp = out_buf_adr;                  /* restore empty buffer */
  215.    }
  216.    assert(outbufp - out_buf_adr < OUTBUFSIZ);
  217.    *outbufp++ = ch;
  218. } /* wr_dchar() */
  219.  
  220.  
  221. /* Code buffer fill routines
  222. **
  223. ** We use a separate function for each code size.
  224. ** Each function unpacks 8 codes from a packed buffer (f)
  225. ** to an unpacked buffer (t)
  226. ** A lot of code space, but really speeds up bit picking.
  227. */
  228. static unsigned char f[13];   /* must be unsigned for right shifts */
  229. static unsigned t[8];
  230.  
  231. static void cb9fill ()
  232. {
  233.    t[0] = (f[0]     ) | ((f[1] &   1) << 8);
  234.    t[1] = (f[1] >> 1) | ((f[2] &   3) << 7);
  235.    t[2] = (f[2] >> 2) | ((f[3] &   7) << 6);
  236.    t[3] = (f[3] >> 3) | ((f[4] &  15) << 5);
  237.    t[4] = (f[4] >> 4) | ((f[5] &  31) << 4);
  238.    t[5] = (f[5] >> 5) | ((f[6] &  63) << 3);
  239.    t[6] = (f[6] >> 6) | ((f[7] & 127) << 2);
  240.    t[7] = (f[7] >> 7) | ((f[8]      ) << 1);
  241. }
  242.  
  243. static void cb10fill ()
  244. {
  245.    t[0] = (f[0]     ) | ((f[1] &   3) << 8);
  246.    t[1] = (f[1] >> 2) | ((f[2] &  15) << 6);
  247.    t[2] = (f[2] >> 4) | ((f[3] &  63) << 4);
  248.    t[3] = (f[3] >> 6) | ((f[4]      ) << 2);
  249.    t[4] = (f[5]     ) | ((f[6] &   3) << 8);
  250.    t[5] = (f[6] >> 2) | ((f[7] &  15) << 6);
  251.    t[6] = (f[7] >> 4) | ((f[8] &  63) << 4);
  252.    t[7] = (f[8] >> 6) | ((f[9]      ) << 2);
  253. }
  254.  
  255. static void cb11fill ()
  256. {
  257.    t[0] = (f[0]     ) | ((f[1] &   7) << 8);
  258.    t[1] = (f[1] >> 3) | ((f[2] &  63) << 5);
  259.    t[2] = (f[2] >> 6) | (f[3] << 2) | ((f[4] &  1) << 10);
  260.    t[3] = (f[4] >> 1) | ((f[5] &  15) << 7);
  261.    t[4] = (f[5] >> 4) | ((f[6] & 127) << 4);
  262.    t[5] = (f[6] >> 7) | (f[7] << 1) | ((f[8] &  3) <<  9);
  263.    t[6] = (f[8] >> 2) | ((f[9] &  31) << 6);
  264.    t[7] = (f[9] >> 5) | ((f[10]     ) << 3);
  265. }
  266.  
  267. static void cb12fill ()
  268. {
  269.    t[0] = (f[0]     )  | ((f[1] & 15) << 8);
  270.    t[1] = (f[1] >> 4)  | ((f[2]     ) << 4);
  271.    t[2] = (f[3]     )  | ((f[4] & 15) << 8);
  272.    t[3] = (f[4] >> 4)  | ((f[5]     ) << 4);
  273.    t[4] = (f[6]     )  | ((f[7] & 15) << 8);
  274.    t[5] = (f[7] >> 4)  | ((f[8]     ) << 4);
  275.    t[6] = (f[9]     )  | ((f[10] & 15) << 8);
  276.    t[7] = (f[10] >> 4) | ((f[11]     ) << 4);
  277. }
  278.  
  279. static void cb13fill ()
  280. {
  281.    t[0] = (f[0] ) | ((f[1] & 31) << 8);
  282.    t[1] = (f[1] >> 5) | (f[2] << 3) | ((f[3] & 3) << 11);
  283.    t[2] = (f[3] >> 2) | ((f[4] & 127) << 6);
  284.    t[3] = (f[4] >> 7) | (f[5] << 1) | ((f[6] & 15) << 9);
  285.    t[4] = (f[6] >> 4) | (f[7] << 4) | ((f[8] & 1) << 12);
  286.    t[5] = (f[8] >> 1) | ((f[9] & 63) << 7);
  287.    t[6] = (f[9] >> 6) | (f[10] << 2) | ((f[11] & 7) << 10);
  288.    t[7] = (f[11] >> 3) | (f[12] << 5);
  289. }
  290.  
  291. /* vector of code buffer fill routines
  292. */
  293. void (*cbfillvec[])  PARMS ((void)) = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
  294.          cb9fill, cb10fill, cb11fill, cb12fill, cb13fill };
  295.  
  296. /* cbfill -- main code buffer fill routine
  297. **
  298. ** moves data from inbuf[] to f[]
  299. ** then calls via vector to unpack to t[]
  300. ** then moves from t[] to codebuf[]
  301. ** A lot of moving around, but still faster than a lot of shifting and
  302. ** masking via variables (at least on a micro -- don't know about VAXen)
  303. **  Uses memcpy() for block move
  304. */
  305.  
  306. static void cbfill ()
  307. {
  308.    char *inbp;
  309.    inbp = in_buf_adr + bit_offset / 8;
  310.    codebufp = codebuf;
  311.    while ( codebufp < codebuflim ) {
  312.      memcpy((VOIDPTR) f, inbp, nbits);
  313.       (*cbfillvec[nbits])();
  314.       memcpy((VOIDPTR) codebufp, (VOIDPTR) t, 8 * sizeof(unsigned int));
  315.       inbp += nbits;
  316.       codebufp += 8;
  317.    }
  318.    bit_offset += nbits * CODEBUF_SIZE;
  319. }
  320.  
  321. /* The following is used in the KwKwK case because it's a pretty rare
  322. ** case, and doing it this way avoids the overhead of remembering the
  323. ** "finchar" (first input character) of every string
  324. */
  325. static int firstchar(code)    /* find first character of a code */
  326. int code;
  327. {
  328.    while ( code > 255 )
  329.       code = head[code];
  330.    return code;
  331. }
  332.  
  333. int lzd(input_f, output_f)
  334. BLOCKFILE input_f, output_f;          /* input & output files */
  335. {
  336.    in_f = input_f;                 /* make it avail to other fns */
  337.    out_f = output_f;               /* ditto */
  338.    nbits = 9;
  339.    max_code = 512;
  340.    free_code = FIRST_FREE;
  341.    bit_offset = 0;
  342.    outbuflim = out_buf_adr + OUTBUFSIZ;   /* setup out buffer limit */
  343.    outbufguard = outbuflim - 12;     /* for checking avail. room in outbuf */
  344.       /* note must allow for as many characters as we special-case (8) */
  345.       /* used 12 for extra fudge factor (Rahul does it, so I can too) */
  346.    outbufp = out_buf_adr;                 /* setup output buffer ptr */
  347.    codebufp = codebuflim = &codebuf[CODEBUF_SIZE]; /* code buf ptr & limit */
  348.    *codebuflim = CLEAR; /* phony CLEAR sentinel past end of code buffer */
  349.  
  350.    if (BLOCKREAD (in_f, in_buf_adr, INBUFSIZ) == -1) /* fill input buffer */
  351.       return(IOERR);
  352.    if (memflag == 0) {
  353.      head = (int *) ealloc((MAXMAX+10) * sizeof(int));
  354.      tail = (char *) ealloc((MAXMAX+10) * sizeof(char));
  355.      stack = (char *) ealloc (sizeof (unsigned) * STACKSIZE + 20);
  356.      memflag++;
  357.    }
  358.  
  359.    stack_pointer = stack_lim = stack + STACKSIZE; /* setup stack ptr, limit*/
  360.    init_dtab();             /* initialize table */
  361.  
  362. loop:
  363.    cur_code = *codebufp++; /* get code from code buffer */
  364.  
  365. goteof: /* special case for CLEAR then Z_EOF, for 0-length files */
  366.    if (cur_code == Z_EOF) {
  367.       debug((printf ("lzd: Z_EOF\n")))
  368.  
  369.       if (outbufp != out_buf_adr) {
  370.           if (BLOCKWRITE (out_f, out_buf_adr, outbufp - out_buf_adr)
  371.                                                   != outbufp - out_buf_adr)
  372.              prterror ('f', "Output error in lzd().\n");
  373.             addbfcrc(out_buf_adr, outbufp - out_buf_adr);
  374.  
  375.       }
  376. #ifdef FILTER
  377.         /* get next two bytes and put them where zoofilt can find them */
  378.         /* nbits known to be in range 9..13 */
  379.         bit_offset = ((bit_offset + 7) / 8) * 8; /* round up to next byte */
  380.         filt_lzd_word = rd_dcode();
  381.         filt_lzd_word |= (rd_dcode() << nbits);
  382.         filt_lzd_word &= 0xffff;
  383. #endif
  384.       return (0);
  385.    }
  386.  
  387.    assert(nbits >= 9 && nbits <= 13);
  388.  
  389.    if (cur_code == CLEAR) {          /* was it sentinel or real CLEAR ? */
  390.       if ( codebufp > codebuflim ) { /* it was the sentinel             */
  391.          if ( bit_offset % 8 == 0 && /* if we're on byte boundary and   */
  392.                    /* codesize won't change before codebuf is filled and */
  393.                    /* codebuf can be filled without running out of inbuf */
  394.                 free_code + CODEBUF_SIZE < max_code &&
  395.                 bit_offset / 8 + (CODEBUF_SIZE * 13 / 8) < INBUFSIZ - 10 ) {
  396.             codebufoffset = bit_offset; /* remember where we were when */
  397.             cbfill();             /* we filled the code buffer */
  398.             codebufp = codebuf;   /* setup code buffer pointer */
  399.             goto loop;            /* now go get codes from code buffer */
  400.          }                 /* otherwise, use rd_dcode to get code */
  401.          codebufp = codebuflim;   /* reset codebuf ptr to sentinel */
  402.          cur_code = rd_dcode();   /* get code via rd_dcode() */
  403.          if ( cur_code != CLEAR ) /* if it's not CLEAR */
  404.             goto got_code;        /* then go handle it */
  405.       } else {          /* else it's really a CLEAR code, not sentinel */
  406.  /* reset bit_offset to get next code in input buf after CLEAR code */
  407.          bit_offset = codebufoffset + (codebufp - codebuf) * nbits;
  408.       }
  409.       codebufp = codebuflim;      /* set code buf ptr to sentinel */
  410.       debug((printf ("lzd: CLEAR\n")))
  411.       init_dtab();                /* init decompression table, etc. */
  412.       old_code = cur_code = rd_dcode(); /* get next code after CLEAR */
  413.         if (cur_code == Z_EOF)        /* special case for 0-length files */
  414.             goto goteof;
  415.       wr_dchar(cur_code);         /* write it out */
  416.       goto loop;                  /* and get next code */
  417.    }
  418.  
  419. got_code: /* we got a code and it's not a CLEAR */
  420.  
  421.    if (cur_code == Z_EOF) {
  422.       debug((printf ("lzd: Z_EOF\n")))
  423.       if (outbufp != out_buf_adr) {
  424.           if (BLOCKWRITE (out_f, out_buf_adr, outbufp - out_buf_adr)
  425.                                                   != outbufp - out_buf_adr)
  426.              prterror ('f', "Output error in lzd().\n");
  427.          addbfcrc(out_buf_adr, outbufp - out_buf_adr);
  428.       }
  429.       return (0);
  430.    }
  431.  
  432.    in_code = cur_code;              /* save original code */
  433.    if (cur_code >= free_code) {        /* if code not in table (k<w>k<w>k) */
  434.       cur_code = old_code;             /* previous code becomes current */
  435.                                        /* push first character of old code */
  436.       *--stack_pointer = firstchar(old_code);
  437.       goto unwind;                     /* and go "unwind" the current code */
  438.    }              /* (use general unwind because the stack isn't empty now) */
  439.  
  440. /* Unwind a code.  The basic idea is to use a sort of loop-unrolling
  441. ** approach to really speed up the processing by treating the codes
  442. ** which represent short strings (the vast majority of codes) as
  443. ** special cases.  Avoid a lot of stack overflow checking safely.
  444. */
  445.  
  446.    if (cur_code > 255) {                  /* if cur_code is not atomic */
  447.       *--stack_pointer = tail[cur_code];  /* push its tail code */
  448.       cur_code = head[cur_code];          /* and replace with its head code */
  449.    } else {                        /* else 1-byte string */
  450.       if ( outbufp > outbufguard ) /* if outbuf near end, */
  451.          goto write_stack;         /* write via general routine */
  452.       *outbufp++ = cur_code;       /* we got space, put char out */
  453.       goto add_code;               /* add code to table */
  454.    }
  455.  
  456.    if (cur_code > 255) {                  /* if cur_code is not atomic */
  457.       *--stack_pointer = tail[cur_code];  /* push its tail code */
  458.       cur_code = head[cur_code];          /* and replace with its head code */
  459.    } else {                        /* else 2-byte string */
  460.       if ( outbufp > outbufguard ) /* if outbuf near end, */
  461.          goto write_stack;         /* write via general routine */
  462.       *outbufp++ = cur_code;       /* we got space, put char out, and */
  463.       goto move_1_char;            /* go move rest of stack to outbuf */
  464.    }
  465.    if (cur_code > 255) {                  /* if cur_code is not atomic */
  466.       *--stack_pointer = tail[cur_code];  /* push its tail code */
  467.       cur_code = head[cur_code];          /* and replace with its head code */
  468.    } else {                        /* else 3-byte string */
  469.       if ( outbufp > outbufguard ) /* if outbuf near end, */
  470.          goto write_stack;         /* write via general routine */
  471.       *outbufp++ = cur_code;       /* we got space, put char out, and */
  472.       goto move_2_char;            /* go move rest of stack to outbuf */
  473.    }
  474.  
  475. /* we handle codes representing strings of 4 thru 8 bytes similarly */
  476.  
  477.    if (cur_code > 255) {
  478.       *--stack_pointer = tail[cur_code];
  479.       cur_code = head[cur_code];
  480.    } else {                        /* 4-byte string */
  481.       if ( outbufp > outbufguard )
  482.          goto write_stack;
  483.       *outbufp++ = cur_code;
  484.       goto move_3_char;
  485.    }
  486.    if (cur_code > 255) {
  487.       *--stack_pointer = tail[cur_code];
  488.       cur_code = head[cur_code];
  489.    } else {                        /* 5-byte string */
  490.       if ( outbufp > outbufguard )
  491.          goto write_stack;
  492.       *outbufp++ = cur_code;
  493.       goto move_4_char;
  494.    }
  495.    if (cur_code > 255) {
  496.       *--stack_pointer = tail[cur_code];
  497.       cur_code = head[cur_code];
  498.    } else {                        /* 6-byte string */
  499.       if ( outbufp > outbufguard )
  500.          goto write_stack;
  501.       *outbufp++ = cur_code;
  502.       goto move_5_char;
  503.    }
  504.    if (cur_code > 255) {
  505.       *--stack_pointer = tail[cur_code];
  506.       cur_code = head[cur_code];
  507.    } else {                        /* 7-byte string */
  508.       if ( outbufp > outbufguard )
  509.          goto write_stack;
  510.       *outbufp++ = cur_code;
  511.       goto move_6_char;
  512.    }
  513.    if (cur_code > 255) {
  514.       *--stack_pointer = tail[cur_code];
  515.       cur_code = head[cur_code];
  516.    } else {                        /* 8-byte string */
  517.       if ( outbufp > outbufguard )
  518.          goto write_stack;
  519.       *outbufp++ = cur_code;
  520.       goto move_7_char;
  521.    }
  522.  
  523. /* Here for KwKwK case and strings longer than 8 bytes */
  524. /* Note we have to check stack here, but not elsewhere */
  525.  
  526. unwind:
  527.    while (cur_code > 255) {               /* if code, not character */
  528.       *--stack_pointer = tail[cur_code];         /* push suffix char */
  529.       if (stack_pointer < stack+12)
  530.          prterror ('f', "Stack overflow in lzd().\n");
  531.       cur_code = head[cur_code];          /* head of code is new code */
  532.    }
  533.  
  534. /* General routine to write stack with check for output buffer full */
  535.  
  536. write_stack:
  537.    assert(nbits >= 9 && nbits <= 13);
  538.    wr_dchar(cur_code);    /* write this code, don't need to stack it first */
  539.    while ( stack_pointer < stack_lim ) {
  540.       wr_dchar(*stack_pointer++);
  541.    }
  542.    goto add_code;                           /* now go add code to table */
  543.  
  544. /* Here to move strings from stack to output buffer */
  545. /* only if we know we have enough room in output buffer */
  546. /* because (outbufp <= outbufguard) */
  547.  
  548. move_7_char:
  549.    *outbufp++ = *stack_pointer++;
  550. move_6_char:
  551.    *outbufp++ = *stack_pointer++;
  552. move_5_char:
  553.    *outbufp++ = *stack_pointer++;
  554. move_4_char:
  555.    *outbufp++ = *stack_pointer++;
  556. move_3_char:
  557.    *outbufp++ = *stack_pointer++;
  558. move_2_char:
  559.    *outbufp++ = *stack_pointer++;
  560. move_1_char:
  561.    *outbufp++ = *stack_pointer++;
  562.  
  563. assert(stack_pointer == stack_lim); /* I haven't tested this! rdg */
  564.  
  565. /* add_code is now inline to avoid overhead of function call on */
  566. /*   each code processed */
  567.  
  568. add_code:
  569.    assert(nbits >= 9 && nbits <= 13);
  570.    assert(free_code <= MAXMAX+1);
  571.    tail[free_code] = cur_code;                /* save suffix char */
  572.    head[free_code] = old_code;                /* save prefix code */
  573.    free_code++;
  574.    assert(nbits >= 9 && nbits <= 13);
  575.    if (free_code >= max_code) {
  576.       if (nbits < MAXBITS) {
  577.          debug((printf("lzd: nbits was %d\n", nbits)))
  578.          nbits++;
  579.          assert(nbits >= 9 && nbits <= 13);
  580.          debug((printf("lzd: nbits now %d\n", nbits)))
  581.          max_code = max_code << 1;        /* double max_code */
  582.          debug((printf("lzd: max_code now %d\n", max_code)))
  583.       }
  584.    }
  585.    old_code = in_code;
  586.  
  587.    assert(nbits >= 9 && nbits <= 13);
  588.  
  589.    goto loop;
  590. } /* lzd() */
  591.  
  592. #else /* SLOW_LZD defined, so use following instead */
  593.  
  594. /*********************************************************************/
  595. /* Original slower lzd().                                            */
  596. /*********************************************************************/
  597.  
  598. /*
  599. Lempel-Ziv decompression.  Mostly based on Tom Pfau's assembly language
  600. code.  The contents of this file are hereby released to the public domain.
  601.                                  -- Rahul Dhesi 1986/11/14
  602. */
  603.  
  604. #define  STACKSIZE   4000
  605.  
  606. struct tabentry {
  607.    unsigned next;
  608.    char z_ch;
  609. };
  610.  
  611. void init_dtab PARMS((void));
  612. unsigned rd_dcode PARMS((void));
  613. void wr_dchar PARMS((int));
  614. void ad_dcode PARMS((void));
  615.  
  616. #ifdef FILTER
  617. /* to send data back to zoofilt */
  618. extern unsigned int filt_lzd_word;
  619. #endif /* FILTER */
  620.  
  621.  
  622. static unsigned stack_pointer = 0;
  623. static unsigned *stack;
  624.  
  625. #define  push(x)  {  \
  626.                      stack[stack_pointer++] = (x);                   \
  627.                      if (stack_pointer >= STACKSIZE)                 \
  628.                         prterror ('f', "Stack overflow in lzd().\n");\
  629.                   }
  630. #define  pop()    (stack[--stack_pointer])
  631.  
  632. extern char *out_buf_adr;        /* output buffer */
  633. extern char *in_buf_adr;         /* input buffer */
  634.  
  635. char memflag = 0;                /* memory allocated? flag */
  636. extern struct tabentry *table;   /* hash table from lzc.c */
  637. static unsigned cur_code;
  638. static unsigned old_code;
  639. static unsigned in_code;
  640.  
  641. static unsigned free_code;
  642. static int nbits;
  643. static unsigned max_code;
  644.  
  645. static char fin_char;
  646. static char k;
  647. static unsigned masks[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
  648.                         0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff };
  649. static unsigned bit_offset;
  650. static unsigned output_offset;
  651.  
  652. #ifdef UNBUF_IO
  653. #define        BLOCKFILE        int
  654. #define        BLOCKREAD        read
  655. #define        BLOCKWRITE        blockwrite
  656. int read PARMS ((int, VOIDPTR, unsigned));
  657. int write PARMS ((int, VOIDPTR, unsigned));
  658. #else
  659. #define        BLOCKFILE        ZOOFILE
  660. #define        BLOCKREAD        zooread
  661. #define        BLOCKWRITE        zoowrite
  662. #endif /* UNBUF_IO */
  663.  
  664. static BLOCKFILE in_f, out_f;
  665.  
  666. int lzd(input_f, output_f)
  667. BLOCKFILE input_f, output_f;          /* input & output file handles */
  668. {
  669.    in_f = input_f;                 /* make it avail to other fns */
  670.    out_f = output_f;               /* ditto */
  671.    nbits = 9;
  672.    max_code = 512;
  673.    free_code = FIRST_FREE;
  674.    stack_pointer = 0;
  675.    bit_offset = 0;
  676.    output_offset = 0;
  677.  
  678.    if (BLOCKREAD (in_f, in_buf_adr, INBUFSIZ) == -1)
  679.       return(IOERR);
  680.    if (memflag == 0) {
  681.      table = (struct tabentry *) ealloc((MAXMAX+10) * sizeof(struct tabentry));
  682.      stack = (unsigned *) ealloc (sizeof (unsigned) * STACKSIZE + 20);
  683.      memflag++;
  684.    }
  685.  
  686.    init_dtab();             /* initialize table */
  687.  
  688. loop:
  689.    cur_code = rd_dcode();
  690. goteof: /* special case for CLEAR then Z_EOF, for 0-length files */
  691.    if (cur_code == Z_EOF) {
  692.       debug((printf ("lzd: Z_EOF\n")))
  693.       if (output_offset != 0) {
  694.          if (BLOCKWRITE (out_f, out_buf_adr, output_offset) != output_offset)
  695.             prterror ('f', "Output error in lzd().\n");
  696.          addbfcrc(out_buf_adr, output_offset);
  697.       }
  698. #ifdef FILTER
  699.         /* get next two bytes and put them where zoofilt can find them */
  700.         /* nbits known to be in range 9..13 */
  701.         bit_offset = ((bit_offset + 7) / 8) * 8; /* round up to next byte */
  702.         filt_lzd_word = rd_dcode();
  703.         filt_lzd_word |= (rd_dcode() << nbits);
  704.         filt_lzd_word &= 0xffff;
  705. #endif
  706.       return (0);
  707.    }
  708.  
  709.    assert(nbits >= 9 && nbits <= 13);
  710.  
  711.    if (cur_code == CLEAR) {
  712.       debug((printf ("lzd: CLEAR\n")))
  713.       init_dtab();
  714.       fin_char = k = old_code = cur_code = rd_dcode();
  715.         if (cur_code == Z_EOF)        /* special case for 0-length files */
  716.             goto goteof;
  717.       wr_dchar(k);
  718.       goto loop;
  719.    }
  720.  
  721.    in_code = cur_code;
  722.    if (cur_code >= free_code) {        /* if code not in table (k<w>k<w>k) */
  723.       cur_code = old_code;             /* previous code becomes current */
  724.       push(fin_char);
  725.    }
  726.  
  727.    while (cur_code > 255) {               /* if code, not character */
  728.       push(table[cur_code].z_ch);         /* push suffix char */
  729.       cur_code = table[cur_code].next;    /* <w> := <w>.code */
  730.    }
  731.  
  732.    assert(nbits >= 9 && nbits <= 13);
  733.  
  734.    k = fin_char = cur_code;
  735.    push(k);
  736.    while (stack_pointer != 0) {
  737.       wr_dchar(pop());
  738.    }
  739.    assert(nbits >= 9 && nbits <= 13);
  740.    ad_dcode();
  741.    old_code = in_code;
  742.  
  743.    assert(nbits >= 9 && nbits <= 13);
  744.  
  745.    goto loop;
  746. } /* lzd() */
  747.  
  748. /* rd_dcode() reads a code from the input (compressed) file and returns
  749. its value. */
  750. unsigned rd_dcode()
  751. {
  752.    register char *ptra, *ptrb;    /* miscellaneous pointers */
  753.    unsigned word;                     /* first 16 bits in buffer */
  754.    unsigned byte_offset;
  755.    char nextch;                           /* next 8 bits in buffer */
  756.    unsigned ofs_inbyte;               /* offset within byte */
  757.  
  758.    ofs_inbyte = bit_offset % 8;
  759.    byte_offset = bit_offset / 8;
  760.    bit_offset = bit_offset + nbits;
  761.  
  762.    assert(nbits >= 9 && nbits <= 13);
  763.  
  764.    if (byte_offset >= INBUFSIZ - 5) {
  765.       int space_left;
  766.  
  767. #ifdef CHECK_BREAK
  768.     check_break();
  769. #endif
  770.  
  771.       assert(byte_offset >= INBUFSIZ - 5);
  772.       debug((printf ("lzd: byte_offset near end of buffer\n")))
  773.  
  774.       bit_offset = ofs_inbyte + nbits;
  775.       space_left = INBUFSIZ - byte_offset;
  776.       ptrb = byte_offset + in_buf_adr;          /* point to char */
  777.       ptra = in_buf_adr;
  778.       /* we now move the remaining characters down buffer beginning */
  779.       debug((printf ("rd_dcode: space_left = %d\n", space_left)))
  780.       while (space_left > 0) {
  781.          *ptra++ = *ptrb++;
  782.          space_left--;
  783.       }
  784.       assert(ptra - in_buf_adr == ptrb - (in_buf_adr + byte_offset));
  785.       assert(space_left == 0);
  786.       if (BLOCKREAD (in_f, ptra, byte_offset) == -1)
  787.          prterror ('f', "I/O error in lzd:rd_dcode.\n");
  788.       byte_offset = 0;
  789.    }
  790.    ptra = byte_offset + in_buf_adr;
  791.    /* NOTE:  "word = *((int *) ptra)" would not be independent of byte order. */
  792.    word = (unsigned char) *ptra; ptra++;
  793.    word = word | ( ((unsigned char) *ptra) << 8 ); ptra++;
  794.  
  795.    nextch = *ptra;
  796.    if (ofs_inbyte != 0) {
  797.       /* shift nextch right by ofs_inbyte bits */
  798.       /* and shift those bits right into word; */
  799.       word = (word >> ofs_inbyte) | (((unsigned)nextch) << (16-ofs_inbyte));
  800.    }
  801.    return (word & masks[nbits]);
  802. } /* rd_dcode() */
  803.  
  804. void init_dtab()
  805. {
  806.    nbits = 9;
  807.    max_code = 512;
  808.    free_code = FIRST_FREE;
  809. }
  810.  
  811. void wr_dchar (ch)
  812. int ch;
  813. {
  814.    if (output_offset >= OUTBUFSIZ) {      /* if buffer full */
  815. #ifdef CHECK_BREAK
  816.     check_break();
  817. #endif
  818.       if (BLOCKWRITE (out_f, out_buf_adr, output_offset) != output_offset)
  819.          prterror ('f', "Write error in lzd:wr_dchar.\n");
  820.       addbfcrc(out_buf_adr, output_offset);     /* update CRC */
  821.       output_offset = 0;                  /* restore empty buffer */
  822.    }
  823.    assert(output_offset < OUTBUFSIZ);
  824.    out_buf_adr[output_offset++] = ch;        /* store character */
  825. } /* wr_dchar() */
  826.  
  827. /* adds a code to table */
  828. void ad_dcode()
  829. {
  830.    assert(nbits >= 9 && nbits <= 13);
  831.    assert(free_code <= MAXMAX+1);
  832.    table[free_code].z_ch = k;                /* save suffix char */
  833.    table[free_code].next = old_code;         /* save prefix code */
  834.    free_code++;
  835.    assert(nbits >= 9 && nbits <= 13);
  836.    if (free_code >= max_code) {
  837.       if (nbits < MAXBITS) {
  838.          debug((printf("lzd: nbits was %d\n", nbits)))
  839.          nbits++;
  840.          assert(nbits >= 9 && nbits <= 13);
  841.          debug((printf("lzd: nbits now %d\n", nbits)))
  842.          max_code = max_code << 1;        /* double max_code */
  843.          debug((printf("lzd: max_code now %d\n", max_code)))
  844.       }
  845.    }
  846. }
  847. #endif /* ! SLOW_LZD */
  848.